package leetcode;
/**
 * 897.递增顺序搜索树
 * 给你一棵二叉搜索树的root，请你按中序遍历将其重新排列为一棵递增顺序搜索树，
 * 使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
 *
 * 输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
 * 输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
 *
 * 输入：root = [5,1,7]
 * 输出：[1,null,5,null,7]
 */
public class Num_897 {
    //实际就是中序遍历重新构建二叉树
    public TreeNode increasingBST(TreeNode root) {
        //边界条件
        if(root == null){
            return null;
        }
        //先递归重构左子树
        TreeNode leftTreeRoot = increasingBST(root.left);
        //再递归重构右子树
        TreeNode rightTreeRoot = increasingBST(root.right);
        //拼接二叉树
        //root的左树置为空
        root.left = null;
        //拼接左树和根节点
        if(leftTreeRoot != null){
            //找到左子树重构后的最后一个右节点
            TreeNode leftTreeRight = leftTreeRoot;
            while(leftTreeRight.right != null){
                leftTreeRight = leftTreeRight.right;
            }
            leftTreeRight.right = root;
        }
        //拼接根节点和右树
        if(rightTreeRoot != null){
            root.right = rightTreeRoot;
        }
        //返回重构之后的二叉树
        return leftTreeRoot == null ? root : leftTreeRoot;
    }
}
